package 牛客算法篇;

/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2024-02-26
 * Time:13:58
 */

/**
 *
 牛客算法篇:BM13 判断一个链表是否为回文结构
 给定一个链表，请判断该链表是否为回文结构。
 回文是指该字符串正序逆序完全一致。
 数据范围： 链表节点数 0≤n≤1050≤n≤105，链表中每个节点的值满足 ∣val∣≤107∣val∣≤107
 示例1
 输入：
 {1}
 返回值：
 true
 */
public class isPail {
    public static void main(String[] args) {
        ListNode a = new ListNode(1);
        ListNode b = new ListNode(2);
        ListNode c = new ListNode(3);
        ListNode d = new ListNode(2);
        ListNode e = new ListNode(1);

        a.next = b;
        b.next = c;
        c.next = d;
        d.next = e;

        isPail(a);
    }
    public static boolean isPail (ListNode head) {
        // write code here
        if (head == null || head.next == null){
            return true;
        }
        //快慢指针寻找中点
        ListNode slow = head;
        ListNode fast = head.next;

        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }

        //对中点后的结点进行反转
        ListNode left = head;
        ListNode right = reversal(slow);


        while (left != null && right != null){
            if (left.val != right.val){
                return false;
            }
            left = left.next;
            right = right.next;
        }
        return true;
    }

    private static ListNode reversal(ListNode head) {
        ListNode cur = head;
        ListNode pre = null;
        while (cur != null){
            ListNode tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
}
